class Goods:
    def __init__(self, weight, value, status):
        # 物品的重量
        self.weight = weight
        # 物品的价值
        self.value = value
        # 0表示未放入包,1表示已经放入包
        self.status = status


def greedy_valueperweight(goods:list, total):
    result = []
    sum_weight = 0
    sum_value = 0
    while True:
        s = strategy(goods, total)
        if s == -1:
            break
        sum_weight += goods[s].weight
        sum_value += goods[s].value
        # 保留两位有效数字
        res = round(goods[s].value / goods[s].weight, 2)
        result.append(res)
        total = total - goods[s].weight
        goods[s].status = 1
        goods.pop(s)
    return result, sum_weight, sum_value


def strategy(goods, total):
    index = -1

    minWeight = goods[0].weight
    maxValue = goods[0].value
    maxSi = maxValue / minWeight

    for i in range(0, len(goods)):
        currentGood = goods[i]
        if currentGood.status == 0 and currentGood.weight <= total and currentGood.value / currentGood.weight > maxSi:
            index = i
            maxSi = currentGood.value / currentGood.weight
        if currentGood.value / currentGood.weight <= maxSi and currentGood.weight == total:
            index = i
    return index


def main():
    goods = [Goods(35, 10, 0), Goods(30, 40, 0), Goods(75, 30, 0), Goods(50, 50, 0),
             Goods(40, 35, 0), Goods(10, 40, 0), Goods(25, 30, 0)]
    result, sum_weight, sum_value = greedy_valueperweight(goods, 150)
    print("--------------按照取最大价值密度贪心策略--------------")
    print("最终总重量为：" + str(sum_weight))
    print("最终总价值为：" + str(sum_value))
    print("密度选取依此选择为：", end='')
    print(result)


if __name__ == '__main__':
    main()
